package gold.digger;

import gold.utils.InputUtil;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC854 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        Map<String, Map<String, Integer>> memo = new HashMap<>();

        public int kSimilarity(String s1, String s2) {
            if (s1.equals("")) return 0;
            if (memo.containsKey(s1) && memo.get(s1).containsKey(s2)) return memo.get(s1).get(s2);
            memo.putIfAbsent(s1, new HashMap<>());
            int result = Integer.MAX_VALUE;
            for (int i = 0; i < s1.length(); i++) {
                if (s1.charAt(i) == s2.charAt(0)) {
                    if (i == 0) {
                        result = Math.min(result, kSimilarity(s1.substring(1), s2.substring(1)));
                    } else {
                        // 把 i 换到第一个来
                        result = Math.min(result, 1 + kSimilarity(s1.substring(1, i) + s1.charAt(0) + s1.substring(i + 1), s2.substring(1)));
                    }
                }
            }
            memo.get(s1).put(s2, result);
            return result;
        }
    }

    public void run() {
        int[] arr = InputUtil.toIntegerArray("[1,2,3]");
        System.out.println(new Solution().toString());
    }

    public static void main(String[] args) throws Exception {
        LC854 an = new LC854();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
